package cn.bellychang.leetcode.question247;

import org.assertj.core.util.Lists;

import java.util.ArrayList;
import java.util.List;

/**
 * A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
 * <p>
 * Find all strobogrammatic numbers that are of length = n.
 * <p>
 * For example,
 * Given n = 2, return ["11","69","88","96"].
 * <p>
 * Hint:
 * <p>
 * Try to use recursion and notice that it should recurse with n - 2 instead of n - 1.
 *
 * @author ChangLiang
 * @date 2021/3/20
 */
public class Solution {

    public List<String> findStrobogrammatic(int n) {

        return findStrobogrammatic(n, n);
    }

    /**
     *
     * @param currSize 当前处理的规模长度
     * @param sourceSize 原规模长度
     * @return
     */
    private List<String> findStrobogrammatic(int currSize, int sourceSize) {

        if (currSize < 0 || sourceSize < 0 || currSize > sourceSize) {
            throw new IllegalArgumentException("invalid input");
        }

        if (currSize == 0) {
            // Lists.emptyList();  那么 n=2 就不对了
            return Lists.list("");
        }
        if (currSize == 1) {
            return Lists.list("0", "1", "8");
        }

        // 将问题规模缩小为n-2
        List<String> tempList = findStrobogrammatic(currSize - 2, sourceSize);

        List<String> result = new ArrayList<>();
        for (int i = 0; i < tempList.size(); i++) {


            String s = tempList.get(i);
            // n=2和n=3 都不会触发这里  即 当前处理的规模长度 与 原规模长度不同时 要考虑添加00的情况

            // 只有当三级递归的时候 会触发 如 n=4 --> n=2 --> n=0
            // n=2 的时候 00 11 88 69 96

            if (currSize != sourceSize) {
                result.add("0" + s + "0");
            }
            result.add("1" + s + "1");
            result.add("8" + s + "8");
            result.add("6" + s + "9");
            result.add("9" + s + "6");
        }

        return result;
    }



}
